P3312 [SDOI2014]数表

发布于 2020-09-12 | 分类于树状数组、莫比乌斯反演 | 5分钟 | 758字数

\sum_{i=1}^n\sum_{j=1}^m \sigma((i,j))

\sum_{d=1}^{\min(n,m)}\sigma(d)\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=d]

SP25158 STARSBC - Star

发布于 2020-09-12 | 分类于数论、欧拉函数 | 1分钟 | 141字数

观察样例可以发现：

发布于 2020-09-12 | 分类于莫比乌斯反演 | 3分钟 | 471字数

这道题的反推还是挺有意思的。

\sum_{i=1}^n\sum_{j=1}^n\sum_{p=1}^{\lfloor \frac{n}{j} \rfloor}\sum_{q=1}^{\lfloor \frac{n}{j} \rfloor}[(i,j)=1][(p,q)=1]

发布于 2020-09-12 | 分类于树形dp | 4分钟 | 750字数

此题有一个神仙结论：最优链上最多包含一个‘2’，且‘2’不能在链的两边。 至于证明过于简单但很麻烦（~~其实是我懒~~），给大家推荐一个博客，点这。

有了这个结论之后，我们就可以愉快的开始树形dp了。

发布于 2020-09-12 | 6分钟 | 905字数

\sum_{i=1}^n\sum_{j=1}^m ij (i,j)\mu^2((i,j))

\sum_{k=1}^{\min(n,m)}\sum_{i=1}^n\sum_{j=1}^m [(i,j)=k]ij k\mu^2(k)

发布于 2020-09-12 | 分类于莫比乌斯反演 | 5分钟 | 716字数

并不会有更好的阅读体验 ~~甚至你在机房还访问不了~~

\prod_{i=1}^n\prod_{j=1}^m (i,j)

发布于 2020-09-10 | 分类于矩阵乘法、状压dp | 5分钟 | 809字数

你得知道题目下表是从 $0$ 开始编号，那么每个棋子只能控制与它距离不大于 $1$ 的行。

所以只需压当前这一行的状态，令 $dp(i,S)$ 表示前 $i$ 行棋子，第 $i$ 的摆放状态为 $S$ 的方案。

那么有转移：

发布于 2020-09-07 | 分类于树上启发式合并(dsu on tree) | 4分钟 | 617字数

和 $u$ 拥有共同的 $k$ 级祖先的点数就是 $u$ 的 $k$ 级祖先的 $k$ 级儿子的数量 $-1$ .

再转换一下就是以 $u$ 的 $k$ 级祖先为根的子树内深度为 $dep_u+k$ 的点的个数 $-1$ 。

然后用 $cnt_d$ 表示深度为 $d$ 的点数，直接 $\text{dsu~on~tree}$ 即可。

发布于 2020-09-05 | 分类于高斯消元 | 3分钟 | 400字数

设原形坐标为 $O$ ,圆上一点坐标为 $A$

由提示得：

r=\sqrt{\sum_{i=1}^n(A_i-O_i)^2}

发布于 2020-09-05 | 分类于期望dp 、高斯消元 | 4分钟 | 580字数

设

dp(i,j)

表示由

(i,j)

走到

(n,m)

的期望步数。

那么显然有转移：

dp(i,j)=1+(up(i,j) \times dp(i+1,j) + down(i,j) \times dp(i-1,j) + left(i,j) \times dp(i,j-1) + right(i,j) \times dp(i,j+1))